package sort;

import java.util.concurrent.ThreadLocalRandom;

/**
 * @author bruin_du
 * @description 排序算法复习二
 * @date 2022/9/25 8:28
 **/
public class SevenSortReview2 {
    public static final ThreadLocalRandom random = ThreadLocalRandom.current();
    public static void insertSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i; j >= 0 && arr[j] > arr[j + 1] ; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

    public static void insertSortOp(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int target = arr[i + 1];
                int j = i;
                for (; j >= 0 && arr[j] > target; j--) {
                    arr[j + 1] = arr[j];
                }
                arr[j + 1] = target;
            }
        }
    }

    public static void insertSortBS(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int target = arr[i + 1];
                int left = 0, right = i - 1;
                while (left <= right) {
                    int mid = (right - left >> 1) + left;
                    if (arr[mid] > target) right = mid - 1;
                    else left = mid + 1;
                }
                for (int j = i; j >= left; j--) {
                    arr[j + 1] = arr[j];
                }
                arr[left] = target;
            }
        }
    }

    public static void shellSort(int[] arr) {
        int gap = arr.length >> 1;
        while (gap >= 1) {
            for (int i = 0; i < arr.length - gap; i++) {
                for (int j = i; j >= 0 && arr[j] > arr[j + gap]; j -= gap) {
                    swap(arr, j, j + gap);
                }
            }
            gap >>= 1;
        }
    }

    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int index = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[index] > arr[j]) {
                    index = j;
                }
            }
            swap(arr, index, i);
        }
    }

    public static void selectionSortOp(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int min = left, max = right;
            for (int i = left; i <= right; i++) {
                if (arr[min] > arr[i]) min = i;
                if (arr[max] < arr[i]) max = i;
            }
            swap(arr, left, min);
            if (left == max) {
                swap(arr, min, right);
            } else {
                swap(arr, max, right);
            }
            left++;
            right--;
        }
    }

    public static void heapSort(int[] arr) {
        for (int i = (arr.length - 2) >> 1; i >= 0; i--) {
            siftDown(arr, i, arr.length);
        }
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, i, 0);
            siftDown(arr, 0, i);
        }
    }

    private static void siftDown(int[] arr, int i, int length) {
        int child = 2 * i + 1;
        if (child >= length) return;
        if (child + 1 < length && arr[child] < arr[child + 1]) {
            child++;
        }
        if (arr[i] < arr[child]) {
            swap(arr, i, child);
        }
        siftDown(arr, child, length);
    }

    public static void bubbleSort(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    public static void quickSort(int[] arr) {
        quickSortHelper(arr, 0, arr.length - 1);
    }

    private static void quickSortHelper(int[] arr, int left, int right) {
        if (left >= right) return;
        int mid = partition2(arr, left, right);
        quickSortHelper(arr, left, mid - 1);
        quickSortHelper(arr, mid + 1, right);
    }

    private static int partition1(int[] arr, int left, int right) {
        int mid = random.nextInt(left, right);
        int v = arr[mid];
        swap(arr, left, mid);
        int i = left;
        for (int j = left + 1; j <= right; j++) {
            if (arr[j] < v) {
                swap(arr, ++i, j);
            }
        }
        swap(arr, i, left);
        return i;
    }

    private static int partition2(int[] arr, int left, int right) {
        int mid = random.nextInt(left, right);
        swap(arr, left, mid);
        int v = arr[left];
        int i = left + 1, j = right;
        while (true) {
            while (i <= j && arr[i] < v) {
                i++;
            }
            while (i <= j && arr[j] > v) {
                j--;
            }
            if (i >= j) break;
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, j, left);
        return j;
    }

    public static void mergeSortVersion2(int[] arr) {
        int[] tmp = new int[arr.length];
        mergeSortHelper(arr, 0, arr.length - 1, tmp);
    }

    private static void mergeSortHelper(int[] arr, int left, int right, int[] tmp) {
        if (left >= right) return;
        int mid = (right - left >> 1) + left;
        mergeSortHelper(arr, left, mid, tmp);
        mergeSortHelper(arr, mid + 1, right, tmp);
        if (arr[mid] > arr[mid + 1]) {
            merge(arr, left, mid, right, tmp);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] tmp) {
        int i = left, j = mid + 1, index = left;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                tmp[index++] = arr[i++];
            } else {
                tmp[index++] = arr[j++];
            }
        }
        while (i <= mid) {
            tmp[index++] = arr[i++];
        }
        while (j <= right) {
            tmp[index++] = arr[j++];
        }
        for (int k = left; k <= right; k++) {
            arr[k] = tmp[k];
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
